Online Judge►LeetCode

[LeetCode] 508 - Most Frequent Subtree Sum

題意

找出所有子樹和頻率最高的值。

解法

DFS ，並利用 Map 紀錄所有和的次數。

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findFrequentTreeSum = function(root) {
  const map = {};
  
  const dfs = (node) => {
    if ( node === null ) return 0 ;
    let sum = 0;
    if ( node.left ){
      sum += dfs(node.left); 
    }
    if ( node.right ){
      sum += dfs(node.right);
    }
    let result = sum + node.val;
    map[result] = map[result] === undefined ? 1 : map[result] + 1 ;
    return result;
  }
  dfs(root);
  return Object.keys(map)
    .map((num) => {
      return { num, amount : map[num] } ; 
    })
    .sort((e1, e2) => e2.amount - e1.amount )
    .filter((el, index, arr) => el.amount === arr[0].amount )
    .map(el => parseInt(el.num))
};